<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
 <meta>
  <!-- Stylesheets -->
  <link href="../web.css" type="text/css" rel="stylesheet"></link>
  <link href="../pygmentize.css" type="text/css" rel="stylesheet"></link>
  <title>VLFeat - Documentation - C API</title>
  <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>

  <!-- Scripts-->
  
 </meta>

 <!-- Body Start -->
 <body>
  <div id="header">
   <!-- Google CSE Search Box Begins -->
   <form action="http://www.vlfeat.org/search.html" method="get" id="cse-search-box" enctype="application/x-www-form-urlencoded">
    <div>
     <input type="hidden" name="cx" value="003215582122030917471:oq23albfeam"></input>
     <input type="hidden" name="cof" value="FORID:11"></input>
     <input type="hidden" name="ie" value="UTF-8"></input>
     <input type="text" name="q" size="31"></input>
     <input type="submit" name="sa" value="Search"></input>
    </div>
   </form>
   <script src="http://www.google.com/coop/cse/brand?form=cse-search-box&amp;lang=en" xml:space="preserve" type="text/javascript"></script>
   <!-- Google CSE Search Box Ends -->
   <h1><a shape="rect" href="../index.html" class="plain"><span id="vlfeat">VLFeat</span><span id="dotorg">.org</span></a></h1>
  </div>
  <div id="headbanner">
   Documentation - C API
  </div>
  <div id="pagebody">
   <div id="sidebar"> <!-- Navigation Start -->
    <ul>
<li><a href="../index.html">Home</a>
</li>
<li><a href="../download.html">Download</a>
</li>
<li><a href="../doc.html">Documentation</a>
<ul>
<li><a href="../mdoc/mdoc.html">Matlab API</a>
</li>
<li><a href="index.html" class='active' >C API</a>
</li>
<li><a href="../man/man.html">Man pages</a>
</li>
</ul></li>
<li><a href="../overview/tut.html">Tutorials</a>
</li>
<li><a href="../applications/apps.html">Applications</a>
</li>
</ul>

   </div> <!-- sidebar -->
   <div id="content">
    
    <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>
    <div class="doxygen">
<div>
<!-- Generated by Doxygen 1.7.5.1 -->
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li class="current"><a href="pages.html"><span>Related&#160;Pages</span></a></li>
      <li><a href="annotated.html"><span>Data&#160;Structures</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
    </ul>
  </div>
</div>
<div class="header">
  <div class="headertitle">
<div class="title">Quick shift image segmentation </div>  </div>
</div>
<div class="contents">
<div class="textblock"><dl class="author"><dt><b>Author:</b></dt><dd>Brian Fulkerson </dd>
<dd>
Andrea Vedaldi</dd></dl>
<p><a class="el" href="quickshift_8h.html">quickshift.h</a> implements an image segmentation algorithm based on the quick shift clustering algorithm <a class="el" href="citelist.html#CITEREF_vedaldi08quick">[12]</a> .</p>
<ul>
<li><a class="el" href="quickshift.html#quickshift-intro">Overview</a></li>
<li><a class="el" href="quickshift.html#quickshift-usage">Usage</a></li>
<li><a class="el" href="quickshift.html#quickshift-tech">Technical details</a></li>
</ul>
<h2><a class="anchor" id="quickshift-intro"></a>
Overview</h2>
<p>Quick shift <a class="el" href="citelist.html#CITEREF_vedaldi08quick">[12]</a> is a fast mode seeking algorithm, similar to mean shift. The algorithm segments an RGB image (or any image with more than one channel) by identifying clusters of pixels in the joint spatial and color dimensions. Segments are local (superpixels) and can be used as a basis for further processing.</p>
<p>Given an image, the algorithm calculates a forest of pixels whose branches are labeled with a distance value (<a class="el" href="quickshift_8h.html#ab116d2dbad717ce889e56ea8335a1463" title="Get parents.">vl_quickshift_get_parents</a>, <a class="el" href="quickshift_8h.html#a675666418f0bc2665be61f0b243a8c1d" title="Get dists.">vl_quickshift_get_dists</a>). This specifies a hierarchical segmentation of the image, with segments corresponding to subtrees. Useful superpixels can be identified by cutting the branches whose distance label is above a given threshold (the threshold can be either fixed by hand, or determined by cross validation).</p>
<p>Parameter influencing the algorithm are:</p>
<ul>
<li><b>Kernel size.</b> The pixel density and its modes are estimated by using a Parzen window estimator with a Gaussian kernel of the specified size (<a class="el" href="quickshift_8h.html#ae54ca4abe8fb6ba0b8a8306d053b7628" title="Set sigma.">vl_quickshift_set_kernel_size</a>). The larger the size, the larger the neighborhoods of pixels considered.</li>
<li><b>Maximum distance.</b> This (<a class="el" href="quickshift_8h.html#ac54275b6b97121f41cf3b64d9e6210a3" title="Set max distance.">vl_quickshift_set_max_dist</a>) is the maximum distance between two pixels that the algorithm considers when building the forest. In principle, it can be infinity (so that a tree is returned), but in practice it is much faster to consider only relatively small distances (the maximum distance can be set to a small multiple of the kernel size).</li>
</ul>
<h2><a class="anchor" id="quickshift-usage"></a>
Usage</h2>
<ul>
<li>Create a new quick shift object (<a class="el" href="quickshift_8h.html#aec706b048c3f4de42a118e242fbd0105" title="Create a quick shift object.">vl_quickshift_new</a>). The object can be reused for multiple images of the same size.</li>
<li>Configure quick shift by setting the kernel size (<a class="el" href="quickshift_8h.html#ae54ca4abe8fb6ba0b8a8306d053b7628" title="Set sigma.">vl_quickshift_set_kernel_size</a>) and the maximum gap (<a class="el" href="quickshift_8h.html#ac54275b6b97121f41cf3b64d9e6210a3" title="Set max distance.">vl_quickshift_set_max_dist</a>). The latter is in principle not necessary, but useful to speedup processing.</li>
<li>Process an image (<a class="el" href="quickshift_8h.html#aebfc7337283b7a8f8be1a1c0fd4f5f92" title="Create a quick shift objet.">vl_quickshift_process</a>).</li>
<li>Retrieve the parents (<a class="el" href="quickshift_8h.html#ab116d2dbad717ce889e56ea8335a1463" title="Get parents.">vl_quickshift_get_parents</a>) and the distances (<a class="el" href="quickshift_8h.html#a675666418f0bc2665be61f0b243a8c1d" title="Get dists.">vl_quickshift_get_dists</a>). These can be used to segment the image in superpixels.</li>
<li>Delete the quick shift object (<a class="el" href="quickshift_8h.html#a9c2a39344fb684d899f22faf358425e8" title="Delete quick shift object.">vl_quickshift_delete</a>).</li>
</ul>
<h2><a class="anchor" id="quickshift-tech"></a>
Technical details</h2>
<p>For each pixel <em>(x,y)</em>, quick shift regards <img class="formulaInl" alt="$ (x,y,I(x,y)) $" src="form_287.png"/> as a sample from a <em>d + 2</em> dimensional vector space. It then calculates the Parzen density estimate (with a Gaussian kernel of standard deviation <img class="formulaInl" alt="$ \sigma $" src="form_288.png"/>)</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ E(x,y) = P(x,y,I(x,y)) = \sum_{x'y'} \frac{1}{(2\pi\sigma)^{d+2}} \exp \left( -\frac{1}{2\sigma^2} \left[ \begin{array}{c} x - x' \\ y - y' \\ I(x,y) - I(x',y') \\ \end{array} \right] \right) \]" src="form_289.png"/>
</p>
<p>Then quick shift construct a tree connecting each image pixel to its nearest neighbor which has greater density value. Formally, write <img class="formulaInl" alt="$ (x',y') >_P (x,y) $" src="form_290.png"/> if, and only if,</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ P(x',y',I(x',y')) > P(x,y,I(x,y))}. \]" src="form_291.png"/>
</p>
<p>Each pixel <em>(x, y)</em> is connected to the closest higher density pixel <em>parent(x, y)</em> that achieves the minimum distance in</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ \mathrm{dist}(x,y) = \mathrm{min}_{(x',y') > P(x,y)} \left( (x - x')^2 + (y - y')^2 + \| I(x,y) - I(x',y') \|_2^2 \right). \]" src="form_292.png"/>
</p>
 </div></div>
     <!-- Doc Here -->
    </div>
   
   </div>
   <div class="clear">&nbsp;</div>
  </div> <!-- pagebody -->
  <div id="footer">
   &copy; 2007-12 Andrea Vedaldi and Brian Fulkerson
  </div> <!-- footer -->

  <!-- Google Analytics Begins -->
  <script xml:space="preserve" type="text/javascript">
   //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {
   var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
   document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
   }
   //]]>
  </script>
  <script xml:space="preserve" type="text/javascript">
    //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {

   try {
   var pageTracker = _gat._getTracker("UA-4936091-2");
   pageTracker._trackPageview();
   } catch(err) {}

   }
   //]]>
  </script>
  <!-- Google Analytics Ends -->
 </body>
</html>

 
